package com.base.dp;

import java.util.Arrays;
import java.util.LinkedList;

public class FindLongestChain {
    public static void main(String[] args) {
        FindLongestChain chain = new FindLongestChain();
        System.out.println(chain.findLongestChain32(new int[][]{{-10, -8}, {8, 9}, {-5, 0}, {6, 10}, {-6, -4}, {1, 7}, {9, 10}, {-4, 7}}));
    }

    public int findLongestChain32(int[][] pairs) {
        // 按照数对的第二个元素进行升序排序
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

        // dp[i] 表示以 pairs[i] 结尾的最长数对链的长度
        int[] dp = new int[pairs.length];
        Arrays.fill(dp, 1); // 初始化 dp 数组

        // 初始化最长数对链的长度
        int max_length = 1;

        // 动态规划求解
        for (int i = 1; i < pairs.length; i++) {
            for (int j = 0; j < i; j++) {
                // 如果当前数对的第一个元素大于等于前一个数对的第二个元素
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);

                }
            }
            max_length = Math.max(max_length, dp[i]);
        }

        return max_length;
    }

    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        int[] dp = new int[n];
        //定义dp[i]表示pairs[i]的最长数对链的长度
        // dp[]{1,1,2}
        int[][] interval = new int[n][2 * n];
        for (int i = 1; i <n; i++) {
            int index =0;
            for (int j = 0; j <i; j++) {
                interval[i][index++] = pairs[j][0];
                interval[i][index++] = pairs[j][1];
            }
        }

        int maxLen = 1;
        Arrays.fill(dp, 1);
        //只计算可能性，不计算具体的值
        for (int i = 1; i < n; i++) {
            //定义一个区间 ,需不需要定义一个区间呢？我没有办法加入啊
            for (int j = 0; j < i; j++) {
                //算出可以连接的区间，然后看当前i能否加入到
                int[] pairI = pairs[i];
                int i1 = pairI[0];
                int i2 = pairI[1];
                if (!exist(interval[i],i1,i2)) {
                    //能连接到前面或者后面，但是不能代表能接入到整个链路里面去
                    //有什么办法可以判断是否能加入到前面的列表中
                    //
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }

            }
            maxLen = Math.max(maxLen, dp[i]); // 更新最长长度
        }
        return maxLen;
    }


    private boolean exist(int[] nums,int a,int b){
        for (int i :nums){
            if (i>a && i< b){
                return true;
            }
        }
        return false;
    }

    public int lengthOfLIS(int[] nums) {
        // 定义 dp[i] 为以 nums[i] 结尾的最长严格递增子序列的长度。
        // 对于每一个 i（从 0 到 nums.length - 1），
        // 我们需要考虑所有 j（从 0 到 i - 1）的情况，
        // 找出能够形成递增序列的 dp[j] 的最大值，然后 dp[i] = dp[j] + 1。
        if (nums == null || nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        int maxLen = 1;
        Arrays.fill(dp, 1); // 初始化dp数组
        //从第二个开始算，当前元素能否加到前面元素的子序列之后，然后更新子序列
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    //dp[i]能否加到dp[j]所表示子序列的后面形成新的子序列，
                    // 更新最长的子序列
                    //
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]); // 更新最长长度
        }

        return maxLen;
    }
}
